Look-and-say 数列

更新时间:2023-06-01 21:25

Look-and-say 数列是数学中的一种数列,它的名字就是它的推导方式:给定第一项之后,后一项是前一项的发音。

基本介绍

1983年11月,在英国剑桥大学教书的著名数学家约翰·霍顿·康威(John Horton Conway) 首先发现了Look-and-say的奥秘。

规则

如果我们把 1 作为Look-and-say 数列的第一项,那么,它的前几项是这样的:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...

在确定了Look-and-say 数列的第一项之后,就可以根据前一项确定后一项的值了,在上面的示例中,我们把 1 作为此种数列的第一项,那么,就可以这样来推导它的其余项了:

第1个是 1 时,记作 1;

...

依此类推。

英国数学家约翰·康威(John Conway) 最早介绍和分析了Look-and-say 数列。

Look-and-say 数列和压缩/解压缩种的游标编码(Run-length encoding)有相似之处。

如果我们从0到9 中的任何数字d开始,那么d将永远是序列的最后一个数字。d不同于1,数列的开始几项如下:

d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …

巴黎综合理工学院的Ilan Vardi率先研究了 d =3 的状况, 约翰·康威(John Conway) 研究了 d=2 的情况,得出了康威常数。

基本性质

增长性

当 d =22 时,很尴尬的事情发生了,Look-and-say 数列的前几项是:

22, 22, 22, 22,22, …

d 不等于 22 时,Look-and-say 数列可无限增长,也就是说可有无限个项。

数字出现的局限性

序列的各个项中,仅包含种子数字(上面提到的 d) 的各个数位上的阿拉伯数字 和 1,2 ,3 这三个阿拉伯数字。

宇宙衰变

康威的宇宙学定理断言,每一个序列最终都将(“衰变”)分裂成一系列的“原子元素”,它们是有限的子序列,不再与它们的邻居相互作用。有92个元素,其中只有1、2和3个数字,约翰·康威以铀元素命名,称这个序列为audioactive。还有两个“超铀元素”元素,分别是1、2和3。

增长率

在Look-and-say 数列 中,如果 表示数列的第n个成员的位数,那么存在比值极限

λ ≈ 1.303577269034...

这个事实由康威首先证明, 这个常数就被称为康威常数,常用 λ 表示。除了种子数字为 22 的Look-and-say 数列,其它此类数列均存在这个极限值。

康威常数λ 作为斜率换算为角度后,大约为 52.5075度。

康威常数还是一个 71次方多项式的唯一解。

图1x轴为种子数(22除外),y轴为10的n次方,

y的变化曲线的颜色代表了不同的种子数:23(红色)、1(蓝色)、13(紫色)、312(绿色)。这些曲线随着项数的增加趋向于直线,其斜率与康威常数一致。

计算机实现

几乎每种编程语言都可实现这个数列,这里给出一个 Go 语言的实现。

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}